package cn.bugstack.xfg.dev.tech.test;

import java.util.Scanner;

/**
 * @Title: test
 * @Author 程志琨
 * @Package cn.bugstack.xfg.dev.tech.test
 * @Date 2025/3/14 13:41
 * @description: 快排
 */
public class test {

    public static void main(String[] args) {

        int[] a = {49, 38, 65, 97, 76, 13, 27, 47};
        quickSort(a, 0, a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }

    }

    //快排算法
    private static void quickSort(int[] nums, int left, int right) {
        int partPoint;
        if(left < right){
            partPoint = partition(nums, left, right);
            quickSort(nums, left, partPoint - 1);
            quickSort(nums, partPoint + 1, right);
        }

    }

    private static int partition(int[] nums, int left, int right) {
        int temp = nums[left];
        while(left < right){
            //右边视角
            while(left < right && nums[right] >= temp){
                right--;
            }
            if(left < right){
                nums[left] = nums[right];
                left++;
            }

            //左边视角
            while(left < right && nums[left] <= temp){
                left++;
            }
            if(left < right){
                nums[right] = nums[left];
                right--;
            }
        }
        nums[left] = temp;
        return left;
    }

}
